class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& mat) {
        int m=mat.size();
        vector<vector<int>>dp(m+1,vector<int>(m+2,INT_MAX));
        for(int i=0;i<m+2;i++)dp[0][i]=0;
        for(int i=1;i<=m;i++)
            for(int j=1;j<=m;j++)
                dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j+1]))+mat[i-1][j-1];
        int res=INT_MAX;
        for(int i=1;i<=m;i++)
        res=min(res,dp[m][i]);
        return res;
    }

};
